﻿#include <iostream>
#include <stdlib.h>
#include "LinkedListNode.h"

static LinkedListNode* isIntersectant(LinkedListNode* head1, LinkedListNode* head2)
{
	LinkedListNode* startCircleNode1 = nullptr;
	bool isCircle1 = isCircleLinkedList(head1, &startCircleNode1);
	LinkedListNode* startCircleNode2 = nullptr;
	bool isCircle2 = isCircleLinkedList(head2, &startCircleNode2);

	if (isCircle1 && isCircle2)
	{
		// 两个有环
		// 先判断环外相交
		auto cur1 = head1;
		int count1 = 0;
		while (cur1 != startCircleNode1)
		{
			++count1;
			cur1 = cur1->next;
		}

		auto cur2 = head2;
		int count2 = 0;
		while (cur2 != startCircleNode2)
		{
			++count2;
			cur2 = cur2->next;
		}

		auto largeList = (count1 > count2) ? head1 : head2;
		auto smallList = (largeList == head1) ? head2 : head1;
		for (int i = 0; i < abs(count1 - count2); i++)
		{
			largeList = largeList->next;
		}

		while (largeList != startCircleNode1 && largeList != startCircleNode2
			&& smallList != startCircleNode1 && smallList != startCircleNode2)
		{
			if (largeList == smallList)
			{
				return largeList;
			}

			largeList = largeList->next;
			smallList = smallList->next;
		}

		// 再判断 环内相交或两个入环点刚好相同的情况
		cur1 = startCircleNode1->next;
		cur2 = startCircleNode2;
		while (true)
		{
			if (cur1 == cur2)
			{
				return cur2;
			}

			if (cur1 == startCircleNode1)
				break;

			cur1 = cur1->next;
		}
	}
	else if ((isCircle1 && !isCircle2) || (!isCircle1 && isCircle2))
	{
		// 一个有环，一个无环
	}
	else
	{
		// 两个无环
		auto nodeCount1 = getLinkedListNodeCount(head1);
		auto nodeCount2 = getLinkedListNodeCount(head2);
		auto largeList = (nodeCount1 > nodeCount2) ? head1 : head2;
		auto smallList = (largeList == head1) ? head2 : head1;
		for (int i = 0; i < abs(nodeCount1 - nodeCount2); i++)
		{
			largeList = largeList->next;
		}

		while (largeList && smallList)
		{
			if (largeList == smallList)
			{
				return largeList;
			}

			largeList = largeList->next;
			smallList = smallList->next;
		}
	}

	return nullptr;
}

static LinkedListNode* makeList(const int* numbers, size_t size, bool existsLoop, int loopIndex)
{
	auto head = new LinkedListNode(numbers[0]);
	auto cur = head;
	for (int i = 1; i < size; i++)
	{
		cur->next = new LinkedListNode(numbers[i]);
		cur = cur->next;
	}

	if (existsLoop)
	{
		auto end = cur;
		cur = head;
		for (int i = 0; i < loopIndex; i++)
		{
			cur = cur->next;
		}

		end->next = cur;
	}

	return head;
}

// 两个单链表相交的一系列问题
// [题目] 给定两个可能有环也可能无环的单链表，头节点head1和head2.请实现一个函数，如果两个链表相交，
//  请返回相交的第一个节点。如果不相交，返回null
// [要求] 如果两个链表的长度之和为N，时间复杂度请达到O(N), 额外空间复杂度请达到O(1)

// 1. 两个无环相交(Y型)
// 2. 两个无环不相交
// 3. 一个有环、一个无环不相交
// 4. 两个有环不相交
// 5. 两个有环相交
int main_TwoLinkedListIntersect()
{
	int numbers[] = { 1,2,3,4,5,6,7,8 };
	size_t size = sizeof(numbers) / sizeof(int);
	auto head = makeList(numbers, size, true, 3);

	int numbers2[] = { 20, 21, 22, 23, 24, 25 };
	size_t size2 = sizeof(numbers2) / sizeof(int);
	auto head2 = makeList(numbers2, size2, false, 4);

	head2->next->next->next->next->next->next = head->next->next;

	LinkedListNode* startCircle = nullptr;
	bool res = isCircleLinkedList(head, &startCircle);
	printf("head: %d 0x%08x %d\n", res, startCircle, startCircle ? startCircle->value : -1);
	res = isCircleLinkedList(head2, &startCircle);
	printf("head2: %d 0x%08x %d\n", res, startCircle, startCircle ? startCircle->value : -1);

	auto intersection = isIntersectant(head, head2);
	printf("0x%08x=%d\n", intersection, intersection ? intersection->value : -1);

	return 0;
}